package com.leetcode.no45;


// https://leetcode-cn.com/problems/jump-game-ii/solution/tiao-yue-you-xi-ii-by-leetcode-solution/

public class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        // [2,3,1,1,4]  len = 5
        int[] dp = new int[len];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = len + 1;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[dp.length - 1];


    }

    public int jump01(int[] nums) {
        int[] dp = new int[nums.length];

        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = nums.length + 1;
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j <= nums[i]; j++ ) {
                if (i + j >= nums.length) {
                    return dp[dp.length - 1];
                }
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }

        return dp[dp.length - 1];
    }

    public int jump03(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }

    public int jump04(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    public int jump05(int[] nums){
        int step, end, now;
        int n = nums.length - 1;

        int max_pos = 0;
        step = now = end = 0;

        while(end < n){
            max_pos = Math.max(max_pos, nums[now] + now);
            if(now == end){
                step++;
                end = max_pos;
            }
            now++;
        }
        return step;
    }

    public int jump06(int[] nums){
        if (nums.length <= 1) return 0;

        int steps = 0; // 当前的步数
        int curAccess = 0; // 在steps步内可以访问到的最远位置
        int nextAccess = nums[0]; // 如果增加1步，最远可以访问的位置

        for (int i = 0; i < nums.length; i++) {
            if (i > curAccess) { // 当前steps步内访问不到，需要增加步数
                // 增加1步
                steps++;
                // 增加1步后，最远可以访问到哪里？nextAccess
                curAccess = nextAccess;
            }
            // 如果增加1步，最远可以扩到哪里
            nextAccess = Math.max(nextAccess, i + nums[i]);
            // if (nextAccess >= nums.length-1) return steps+1; // 【提前退出】加上反而更慢
        }

        return steps;
    }
}
